﻿namespace AdvancedTraining.Lesson10;

// 本题测试链接 : https://leetcode.cn/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
public class BstToDoubleLinkedList
{
    // 提交下面的代码
    public static Node? TreeToDoublyList(Node? head)
    {
        if (head == null) return null;
        var allInfo = Process(head);
        allInfo.End!.Right = allInfo.Start;
        allInfo.Start!.Left = allInfo.End;
        return allInfo.Start;
    }

    private static Info Process(Node? x)
    {
        if (x == null) return new Info(null, null);
        var lInfo = Process(x.Left);
        var rInfo = Process(x.Right);
        if (lInfo.End != null) lInfo.End.Right = x;
        x.Left = lInfo.End;
        x.Right = rInfo.Start;
        if (rInfo.Start != null) rInfo.Start.Left = x;
        // 整体链表的头    lInfo.start != null ? lInfo.start : X
        // 整体链表的尾    rInfo.end != null ? rInfo.end : X
        return new Info(lInfo.Start ?? x, rInfo.End ?? x);
    }

    public static void Run()
    {
        Console.WriteLine("BST转双向链表算法测试开始");

        // 测试用例1: 空树
        Console.WriteLine("测试用例1: 空树");
        var result1 = TreeToDoublyList(null);
        Console.WriteLine(result1 == null ? "通过: 空树返回null" : "失败: 空树应该返回null");

        // 测试用例2: 单节点树
        Console.WriteLine("\n测试用例2: 单节点树 [4]");
        var singleNode = new Node(4);
        var result2 = TreeToDoublyList(singleNode);
        Console.WriteLine(result2?.Value == 4 ? "通过: 单节点转换成功" : "失败: 单节点转换失败");
        Console.WriteLine($"结果: {result2?.Value}, 左节点: {result2?.Left?.Value}, 右节点: {result2?.Right?.Value}");

        // 测试用例3: 完全二叉树 [4,2,6,1,3,5,7]
        Console.WriteLine("\n测试用例3: 完全二叉树 [4,2,6,1,3,5,7]");
        var root3 = BuildBST(new int[] { 4, 2, 6, 1, 3, 5, 7 });
        var result3 = TreeToDoublyList(root3);
        PrintDoublyList(result3, "期望: 1<->2<->3<->4<->5<->6<->7(循环)");

        // 测试用例4: 左斜树 [5,4,3,2,1]
        Console.WriteLine("\n测试用例4: 左斜树 [5,4,3,2,1]");
        var root4 = BuildBST(new int[] { 5, 4, 3, 2, 1 });
        var result4 = TreeToDoublyList(root4);
        PrintDoublyList(result4, "期望: 1<->2<->3<->4<->5(循环)");

        // 测试用例5: 右斜树 [1,2,3,4,5]
        Console.WriteLine("\n测试用例5: 右斜树 [1,2,3,4,5]");
        var root5 = BuildBST(new int[] { 1, 2, 3, 4, 5 });
        var result5 = TreeToDoublyList(root5);
        PrintDoublyList(result5, "期望: 1<->2<->3<->4<->5(循环)");

        // 测试用例6: 随机树
        Console.WriteLine("\n测试用例6: 随机树 [8,3,10,1,6,14,4,7,13]");
        var root6 = BuildBST(new int[] { 8, 3, 10, 1, 6, 14, 4, 7, 13 });
        var result6 = TreeToDoublyList(root6);
        PrintDoublyList(result6, "期望: 1<->3<->4<->6<->7<->8<->10<->13<->14(循环)");

        Console.WriteLine("\nBST转双向链表算法测试结束");
    }

    /// <summary>
    /// 构建二叉搜索树
    /// </summary>
    private static Node? BuildBST(int[] values)
    {
        Node? root = null;
        foreach (var value in values)
        {
            root = InsertIntoBST(root, value);
        }
        return root;
    }

    /// <summary>
    /// 向二叉搜索树中插入节点
    /// </summary>
    private static Node InsertIntoBST(Node? root, int val)
    {
        if (root == null)
        {
            return new Node(val);
        }

        if (val < root.Value)
        {
            root.Left = InsertIntoBST(root.Left, val);
        }
        else if (val > root.Value)
        {
            root.Right = InsertIntoBST(root.Right, val);
        }

        return root;
    }

    /// <summary>
    /// 打印双向链表
    /// </summary>
    private static void PrintDoublyList(Node? head, string expected)
    {
        if (head == null)
        {
            Console.WriteLine("链表为空");
            return;
        }

        Console.Write("实际: ");
        var current = head;
        var values = new List<int>();

        // 遍历一遍链表
        do
        {
            values.Add(current.Value);
            current = current.Right;
        } while (current != null && current != head);

        Console.WriteLine($"[{string.Join("<->", values)}](循环)");
        Console.WriteLine(expected);

        // 验证循环链表
        bool isCircular = false;
        if (head.Left != null)
        {
            isCircular = head.Left.Right == head;
        }
        Console.WriteLine($"循环链表验证: {(isCircular ? "通过" : "失败")}");

        // 验证有序性
        bool isSorted = true;
        for (int i = 1; i < values.Count; i++)
        {
            if (values[i] <= values[i - 1])
            {
                isSorted = false;
                break;
            }
        }
        Console.WriteLine($"有序性验证: {(isSorted ? "通过" : "失败")}");
    }

    // 提交时不要提交这个类
    public class Node(int data)
    {
        public Node? Left;
        public Node? Right;
        public int Value = data;
    }

    public class Info(Node? start, Node? end)
    {
        public readonly Node? End = end;
        public readonly Node? Start = start;
    }
}